package com.zzy.algorithm.sort;

/**
 * 计数排序
 */
public class Q32_CountingSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
        countingSort(nums);
        for(int x : nums){
            System.out.println(x);
        }
    }


    private static void countingSort(int[] nums){
        int min = nums[0];
        int max = nums[0];
        for(int x : nums){
            if(x > max){
                max = x;
            }
            if(x < min){
                min = x;
            }
        }
        int[] array = new int[max-min+1];
        for(int x : nums){
            int index = x - min;
            array[index] = array[index] + 1;
        }
        int index = 0;
        int arrayIndex = 0;
        while(index <= nums.length -1){
            int count = array[arrayIndex];
            while (count > 0){
                nums[index] = arrayIndex+min;
                index++;
                count--;
            }
            arrayIndex++;
        }
    }

}
